package com.springboot.java.design.search;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: TongRui乀
 * @Date: 2020-09-01 16:56
 * @description： 最大频率栈
 */
public class FreqStack {

    Map<Integer, Integer> freq;
    Map<Integer, Stack<Integer>> group;
    int maxfreq;

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxfreq = 0;
    }

    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        if (f > maxfreq) maxfreq = f;
        group.computeIfAbsent(f, z-> new Stack()).push(x);
    }

    public int pop() {
        int x = group.get(maxfreq).pop();
        freq.put(x, freq.get(x) - 1);
        if (group.get(maxfreq).size() == 0)
            maxfreq--;
        return x;
    }

    public static void main(String[] args) {

        FreqStack stack = new FreqStack();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(1);
        stack.push(4);
        stack.push(5);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }

}
